1. Field of the Invention
The present invention relates to the field of computer systems. More specifically, the present invention relates to manipulation of structures organized as directed acyclic graph structure networks on these computer systems.
2. Background
In many computer applications, the fundamental data elements are first organized into structures comprising non-structure-invoking and structure-invoking elements. The non-structure-invoking elements include various primitives having attributes, and functions for altering the values of the attributes. The structures are further organized into directed acyclic graph (DAG) structure networks in accordance to the way they invoke each other. Traversal is the process by which the structure elements of an instance of a DAG structure is processed. Associated with each traversal process is a traversal state list comprising the current traversal state attribute values. Since the traversal of an invoked structure may affect the traversal state attribute values, the traversal state attribute values are typically saved when invoking another structure, and restored upon returning from the invoked structure. For simplicity, the savings and restorings are often performed without regard to the fact whether the traversal state attributes are going to be affected by the traversal of the invoked structure.
A particular example of such data organization and manipulation is the Programmer's Hierarchical Interactive Graphics System (PHIGS). PHIGS is a functional interface between an application program and a configuration of graphical input and output devices in a computer system. The PHIGS interface provides a high level abstraction of the graphical functions, such that hardware peculiarities are shielded from the application program. Under PHIGS, application specific and graphical data are stored in a centralized hierarchical structure, known as the centralized structure store (CSS). The fundamental entity of data is a structure element and these are grouped together into units called structures. A structure comprises non-structure-invoking elements, i.e. output primitive structure elements such as polyline and polymarks, attribute specification structure elements such as set polyline width (PLW) and polyline color (PLC), and transformation and clipping structure elements such as set local transformation and set modeling clipping volume, and structure-invoking elements, i.e. the control structure element, execute structure. The structures are further organized as DAG structure networks.
To display an instance of a structure network, it is first posted identifying the structure network for display. The structure network is then traversed: staring from the top of the network, the structure elements are interpreted, one structure element at a time. At the start of traversal, the traversal state list for storing the current state values is created. The effect of interpreting a structure element depends on nature of the structure element. When an execute structure element is interpreted, the following actions occur:
a) traversal of the current structure is suspended; PA1 b) the current state values of the traversal state list is saved; PA1 c) global and local modeling transformation are set; PA1 d) the executed structure network is completely traversed; PA1 e) the saved PHIGS traversal state list values are restored; PA1 f) traversal of the current structure is resumed.
The traversal state list comprises over 50 current state attribute values. Each time an execute structure element is interpreted during a traversal, the 50 plus current state attribute values have to be saved and subsequently restored. Additionally, each instance of a posted structure network is completely retraversed, each time the posted structure network is changed. As a result, there are a lot of state attribute value savings and restorings. Since, in many cases, the state attribute values are unaffected by the invoked structure, their savings and restorings are unnecessary.
For further description of PHIGS, see American National Standard X3.144--1988, Computer Graphics--Programmer's Hierarchical Interactive Graphics System (PHIGS) Functional Description, published by the American National Standards Institute, Inc.
Thus, it is desirable if the unaffected state attributes of a DAG structure network can be identified, and the savings and restorings of their current values can be avoided, when one structure invokes another for traversal. As will be disclosed, the present invention provides a method and apparatus for saving and restoring traversal state attribute values of a DAG structure network for a parent structure when it invokes a child structure for traversal that achieves the desired results.